class Heap {
  constructor(compare) {
    this.heap = [];
    this.compare = compare;
  }
  size() {
    return this.heap.length;
  }
  isEmpty() {
    return this.heap.length === 0;
  }
  peek() {
    return this.heap[0] ?? undefined;
  }
  push(value) {
    this.heap.push(value);
    this.bubbleUp(this.heap.length - 1);
  }
  bubbleUp(index) {
    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);
      if (this.compare(this.heap[index], this.heap[parentIndex]) < 0) {
        [this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]];
        index = parentIndex;
      } else break;
    }
  }
  pop() {
    if (this.isEmpty()) return undefined;
    const top = this.heap[0];
    const last = this.heap.pop();
    if (!this.isEmpty()) {
      this.heap[0] = last;
      this.sinkDown(0);
    }
    return top;
  }
  sinkDown(index) {
    let current = index;
    const length = this.size();
    while (true) {
      const left = 2 * current + 1;
      const right = 2 * current + 2;
      let target = current;
      if (left < length && this.compare(this.heap[left], this.heap[target]) < 0)
        target = left;
      if (right < length && this.compare(this.heap[right], this.heap[target]) < 0)
        target = right;
      if (target !== current) {
        [this.heap[current], this.heap[target]] = [this.heap[target], this.heap[current]];
        current = target;
      } else break;
    }
  }
  update(oldValue, newValue) {
    const index = this.heap.indexOf(oldValue);
    if (index === -1) return false;
    this.heap[index] = newValue;
    this.bubbleUp(index);
    this.sinkDown(index);
    return true;
  }
  remove(value) {
    const index = this.heap.indexOf(value);
    if (index === -1) return false;
    const last = this.heap.pop();
    if (index === this.heap.length) return true;
    this.heap[index] = last;
    this.bubbleUp(index);
    this.sinkDown(index);
    return true;
  }
  contains(value) {
    return this.heap.includes(value);
  }
}

class State {
  constructor(id, distFromStart) {
    // 图节点的 id
    this.id = id;
    // 从 start 节点到当前节点的距离
    this.distFromStart = distFromStart;
  }
}

// 输入一幅图和一个起点 start，计算 start 到其他节点的最短距离
var dijkstra = function (start, graph) {
  // 图中节点的个数
  const V = graph.size();
  // 记录最短路径的权重，你可以理解为 dp table
  // 定义：distTo[i] 的值就是节点 start 到达节点 i 的最短路径权重
  const distTo = new Array(V);
  // 求最小值，所以 dp table 初始化为正无穷
  distTo.fill(Infinity);
  // base case，start 到 start 的最短距离就是 0
  distTo[start] = 0;

  // 优先级队列，distFromStart 较小的排在前面
  const pq = new Heap((a, b) => a.distFromStart - b.distFromStart);

  // 从起点 start 开始进行 BF
  pq.push(new State(start, 0));

  while (!pq.isEmpty()) {
    const curState = pq.pop();
    const curNodeID = curState.id;
    const curDistFromStart = curState.distFromStart;

    if (curDistFromStart > distTo[curNodeID]) {
      // 已经有一条更短的路径到达 curNode 节点了
      continue;
    }
    // 将 curNode 的相邻节点装入队列
    for (const nextNodeID of graph.neighbors(curNodeID)) {
      // 看看从 curNode 达到 nextNode 的距离是否会更短
      const distToNextNode = distTo[curNodeID] + graph.weight(curNodeID, nextNodeID);
      if (distTo[nextNodeID] > distToNextNode) {
        // 更新 dp table
        distTo[nextNodeID] = distToNextNode;
        // 将这个节点以及距离放入队列
        pq.push(new State(nextNodeID, distToNextNode));
      }
    }
  }
  return distTo;
};

// test
class Graph {
  constructor(n) {
    this.n = n;
    this.edges = new Array(n).fill(0).map(() => []);
  }
  addEdge(s, t, w) {
    this.edges[s].push({ t, w });
  }
  size() {
    return this.n;
  }
  neighbors(x) {
    return this.edges[x].map((edge) => edge.t);
  }
  weight(x, y) {
    for (const edge of this.edges[x]) {
      if (edge.t === y) return edge.w;
    }
    return Infinity;
  }
}

const graph = new Graph(6);
graph.addEdge(0, 1, 10);
graph.addEdge(0, 4, 15);
graph.addEdge(1, 2, 15);
graph.addEdge(1, 3, 2);
graph.addEdge(2, 5, 5);
graph.addEdge(3, 2, 1);
graph.addEdge(3, 5, 12);
graph.addEdge(4, 5, 10);

console.log(dijkstra(0, graph)); // [0, 10, 13, 12, 15, 18]